#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	int openLock(vector<string>& deadends, string target) {
		unordered_set<string> deads { deadends.begin(), deadends.end() };
		unordered_set<string> F, R, vis;

		int step = 0;
		F.emplace("0000");
		R.emplace(target);

		while (!F.empty() && !R.empty()) {
			unordered_set<string> temp;

			for (auto& cur : F) {
				if (deads.count(cur))
					continue;
				if (R.count(cur))
					return step;
				vis.emplace(cur);

				for (int i = 0; i < 4; i++) {
					string up = plusOne(cur, i);
					if (!vis.count(up))
						temp.emplace(up);
					string down = minusOne(cur, i);
					if (!vis.count(down))
						temp.emplace(down);
				}
			}
			step++;
			F = R;
			R = temp;
		}
		return -1;
	}

private:
	string plusOne(string s, int j) {
		if (s[j] == '9')
			s[j] = '0';
		else
			s[j] += 1;
		return s;
	}

	string minusOne(string s, int j) {
		if (s[j] == '0')
			s[j] = '9';
		else
			s[j] -= 1;
		return s;
	}
};

int main()
{
	return 0;
}
